/**
 *	4.4.质数就是只能被1和本身整除的整数，Eratosthenes筛选法是一种计算质数的有效办法。
 *	这个算法的第一步就是写下所有从2至某个上限之间的所有整数，在算法剩余部分，你遍历整个列表并剔除所有不是质数的整数。
 *
 *	后面的步骤是这样的，找到列表中的第一个不被剔除的数也就是2,然后将列表中所有2的倍数全部剔除，因为它们都可以被2整除，
 *	因此不是质数。接着，再回到列表的头部重新开始，此时列表中尚未被剔除的第一个数是3,所以在3之后把每逢第3个数的倍数剔除，
 *	完成这一步骤之后，再回到列表开头，3后面的下一个数是4,但它是2的倍数，已经被剔除，所以将其跳过，
 *	轮到5,将所有5的倍数全部剔除，这样以此类推，反复执行，最后列表中未被剔除的数均为质数。
 *
 *	编写一个程序，实现这个算法，使用数组表示你的列表。每个数组元素的值用于标记对应的数是否剔除。
 *	开始时所有元素的值都设置为FALSE。如果你的程序运行于16位机器上，小心考虑是不是需要把某个变量声明为long。
 *	一开始先使用包含1000个元素的数组。如果你使用字符数组，使用相同的空间，你将会比使用整数数组找到更多的质数，
 *	你可以使用下标来表示指向数组首元素和尾元素的指针，但你应该使用指针来访问数组元素。
 *
 *	注意除了2以外，所有的偶数都不是质数，稍微多想一下，你可以使程序的空间效率大为提高，
 *	方法是数组中的所有元素只对应奇数，这样，你在相同的数组空间内，你可以寻找到的质数的个数大约是原先的两倍。
**/

/*关于筛选法选质数我已经在第四章编程练习的第二题中给出了代码
接下来我将写出以字符数组为存储单位
以及在数组中仅使用奇数的方法筛选质数*/

#include <stdio.h>
#include <math.h>

#define MAX 5000

char prime[MAX];
int rec[MAX], cnt;

void Eratosthenes(char []);
void init_prime_table(int n);

int main()
{
    int i;
    int count = 0;

    for(i = 1; i < MAX; i++)
        prime[i] = 1;

    printf("the prime range is 2 to %d\n",MAX * 2 + 1);
    Eratosthenes(prime);
    //init_prime_table(MAX);
    printf("2\n");
    for(i = 1; i < MAX; i++){
        if(prime[i] == 1){
            printf("%d ",i * 2 + 1);
	    //printf("%d ", i);
            count++;
        }
        if(count % 10 == 0)
            printf("\n");
    }
    printf("\n");
}

void Eratosthenes(char prime[])
{
    int i = 0;
    int i_p;
    int j;
    int j_p;
    for(i = 1; i < sqrt(MAX); i++){
        if(prime[i]){
            i_p = 2 * i + 1;
            for(j = 2 * i_p; j < MAX * 2 + 1; j += i_p)
                if(j % 2 == 1){
                    j_p = (j - 1)/2;
                    prime[j_p] = 0;
                }
        }
    }
}

void init_prime_table(int n)
{
	int i, j;
	cnt = 0;
	for(i = 0; i < MAX; i++)
		prime[i] = 1;
	prime[0] = prime[1] = 0;
	for(i = 2; i <= n; ++i)
	{
		if(prime[i])
			rec[cnt++] = i;
		// 此处边界判断为rec[j] <= n / i, 如果写成 i * rec[j] <= n, 需要确保 i * rec[j] 不会溢出 int
		for(j = 0; j < cnt && rec[j] <= n / i; ++j)
		{
			prime[i*rec[j]] = 0;
			if(i % rec[j] == 0)
				break;
		}
	}
}
